﻿// Nearest Common Ancestors POJ - 1330.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://vjudge.net/problem/POJ-1330#author=GPT_zh

根树是计算机科学和工程中一个众所周知的数据结构。下面是一个例子:


在图中，每个节点都标有来自{1, 2,...,16}的整数。节点8是树的根。如果节点x在根和节点y之间的路径上，那么节点x是节点y的祖先。例如，节点4是节点16的祖先。节点10也是节点16的祖先。事实上，节点8、4、10和16都是节点16的祖先。请记住，节点本身也是其祖先。节点8、4、6和7是节点7的祖先。如果节点x是节点y和节点z的祖先，那么节点x被称为节点y和z的共同祖先。因此，节点8和4是节点16和7的共同祖先。如果x是y和z的共同祖先并且在y和z的共同祖先中离y和z最近，那么节点x被称为节点y和z的最近共同祖先。因此，节点16和7的最近共同祖先是节点4。节点4比节点8更接近节点16和7。

对于其他例子，节点2和3的最近共同祖先是节点10，节点6和13的最近共同祖先是节点8，节点4和12的最近共同祖先是节点4。在最后一个例子中，如果y是z的祖先，那么y和z的最近共同祖先是y。

编写一个程序，找到树中两个不同节点的最近共同祖先。

输入
输入包括T个测试用例。输入文件的第一行给出测试用例的数量T。每个测试用例以包含一个整数N的行开始，N是树中节点的数量，2≤N≤10,000。节点用整数1, 2,..., N标记。接下来的N-1行中，每行包含一对整数，表示一条边--第一个整数是第二个整数的父节点。请注意，具有N个节点的树恰好有N-1条边。每个测试用例的最后一行包含两个不同的整数，需要计算它们的最近共同祖先。
输出
每个测试用例输出一行。该行应包含一个整数，即最近共同祖先。

2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5

4
3


*/
int main()
{
    std::cout << "Hello World!\n";
}

 